#include<iostream>
#include<vector>
using namespace std;

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> f(n, vector<int>(3));
    vector<vector<int>> g(n, vector<int>(3));
    f[0][0] = -prices[0], f[0][1] = f[0][2] = -0x3f3f3f3f;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
            g[i][j] = g[i - 1][j];
            if (j - 1 >= 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
        }
    }
    return max({ g[n - 1][0],g[n - 1][1],g[n - 1][2] });
}

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> f(n, vector<int>(k + 1));
    vector<vector<int>> g(n, vector<int>(k + 1));
    f[0][0] = -prices[0];
    for (int i = 1; i < k + 1; i++)
        f[0][i] = -0x3f3f3f3f;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < k + 1; j++)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);

            g[i][j] = g[i - 1][j];
            if (j - 1 >= 0) g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
        }
    }
    int ret = 0;
    for (int i = 0; i < k; i++)
    {
        if (g[n - 1][i] < g[n - 1][i + 1]) ret = g[n - 1][i + 1];
    }
    return ret;
}

int main()
{
    vector<int> v{ 1,5,3,65,64 };
    maxProfit(v);
    maxProfit(2, v);

	return 0;
}